Generalized abbreviation

Time: O(Nx2^N); Space: O(N); medium

Write a function to generate the generalized abbreviations of a word.(order does not matter)

Example 1:

Input: word = “word”

Output: [“word”, “1ord”, “w1rd”, “wo1d”, “wor1”, “2rd”, “w2d”, “wo2”, “1o1d”, “1or1”, “w1r1”, “1o2”, “2r1”, “3d”, “w3”, “4”]

Example 2:

Input: word = “today”

Output: [“1o1a1”,“1o1ay”,“1o2y”,“1o3”,“1od1y”,“1od2”,“1oda1”,“1oday”,“2d1y”,“2d2”,“2da1”,“2day”,“3a1”,“3ay”,“4y”,“5”,“t1d1y”,“t1d2”,“t1da1”,“t1day”,“t2a1”,“t2ay”,“t3y”,“t4”,“to1a1”,“to1ay”,“to2y”,“to3”,“tod1y”,“tod2”,“toda1”,“today”]

[1]:

class Solution1(object):
    """
    Time: O(N*2^N)
    Space: O(N)
    """
    def generateAbbreviations(self, word):
        """
        :type word: str
        :rtype: List[str]
        """
        def generateAbbreviationsHelper(word, i, cur, res):
            if i == len(word):
                res.append(''.join(cur))
                return
            cur.append(word[i])

            generateAbbreviationsHelper(word, i + 1, cur, res)

            cur.pop()
            if not cur or not cur[-1][-1].isdigit():
                for l in range(1, len(word) - i + 1):
                    cur.append(str(l))
                    generateAbbreviationsHelper(word, i + l, cur, res)
                    cur.pop()

        res, cur = [], []
        generateAbbreviationsHelper(word, 0, cur, res)
        return res

[4]:

s = Solution1()

word = "word"
# print(s.generateAbbreviations(word))
# ['word', 'wor1', 'wo1d', 'wo2', 'w1rd', 'w1r1', 'w2d', 'w3', '1ord', '1or1',
# '1o1d', '1o2', '2rd', '2r1', '3d', '4']

# assert s.generateAbbreviations(word) == ["word", "1ord", "w1rd", "wo1d", "wor1",
#                                          "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1",
#                                          "1o2", "2r1", "3d", "w3", "4"]

word = "today"
# print(s.generateAbbreviations(word))
# ['today', 'toda1', 'tod1y', 'tod2', 'to1ay', 'to1a1', 'to2y', 'to3', 't1day', 't1da1', 't1d1y', 't1d2', 't2ay',
# 't2a1', 't3y', 't4', '1oday', '1oda1', '1od1y', '1od2', '1o1ay', '1o1a1', '1o2y', '1o3', '2day', '2da1', '2d1y',
# '2d2', '3ay', '3a1', '4y', '5']

# assert s.generateAbbreviations(word) == ["1o1a1","1o1ay","1o2y","1o3","1od1y","1od2","1oda1","1oday",
#                                          "2d1y","2d2","2da1","2day","3a1","3ay","4y","5",
#                                          "t1d1y","t1d2","t1da1","t1day","t2a1","t2ay","t3y","t4",
#                                          "to1a1","to1ay","to2y","to3","tod1y","tod2","toda1","today"]